#ifndef STRMATCH_HPP
#define STRMATCH_HPP

template <size_t MaxPattern>
class z_matcher
{
    typedef size_t size_type;
    const char *_pattern;
    size_type _pattern_len;
    size_type Z[MaxPattern];
public:
    z_matcher() : _pattern(0), _pattern_len(0) { }
    void set_pattern(const char *P)
    {
        _pattern = P;
        if (P[0] == 0) /* pattern is empty */
        {
            _pattern_len = 0;
            return;
        }

        size_type L, R, j, k;

        /* Compute and store Z[k] for each 1 <= k < |P|. */
        Z[0] = L = R = 0;
        for (k = 1; P[k]; k++)
        {
            if (k >= R) /* P[k] is not covered by the Z-box [L,R) */
            {
                for (j = 0; P[j] == P[k+j]; j++);
                L = k;
                R = k + j;
                Z[k] = j;
            }
            else /* P[k] is covered by the Z-box [L,R). */
            {
                size_type kk = k - L;
                if (Z[kk] < R - k)
                {
                    Z[k] = Z[kk];
                }
                else
                {
                    for (j = R - k; P[j] == T[k+j]; j++);
                    L = k;
                    R = k + j;
                    Z[k] = j;
                }
            }
        }
        _pattern_len = k;
    }

    size_type count_matches(const char *T) const
    {
        size_type count = 0;
        size_type j, k, z, L, R;

        /* Compute Z[k] (and store in z) for each 0 <= k < |T|. */
        z = L = R = 0;
        for (k = 0; T[k]; k++)
        {
            if (k >= R) /* P[k] is not covered by the Z-box [L,R) */
            {
                for (j = 0; P[j] && P[j] == T[k+j]; j++);
                L = k;
                R = k + j;
                z = j;
            }
            else /* P[k] is covered by the Z-box [L,R). */
            {
                size_type kk = k - L;
                if (Z[kk] < R - k)
                {
                    z = Z[kk];
                }
                else
                {
                    for (j = R - k; P[j] && P[j] == T[k+j]; j++);
                    L = k;
                    R = k + j;
                    z = j;
                }
            }
            if (z == _pattern_len)
                ++count;
        }
        return count;
    }
};

template <size_t MaxPattern>
class kmp_matcher
{
    typedef size_t size_type;
    const char *_pattern;
    size_type _pattern_len;
    size_type sp[MaxPattern];
public:
    kmp_matcher() : _pattern(0), _pattern_len(0) { }
    void set_pattern(const char *P)
    {
        _pattern = P;
        if (P[0] == 0) /* pattern is empty */
        {
            _pattern_len = 0;
            return;
        }

        /* Compute and store sp[k] for each 0 <= k < |P|. 
         * sp[k] = length of the longest proper prefix of P[0..k] that is
         * also a suffix of P[0..k].
         */
        size_type k;
        sp[0] = 0;
        for (k = 1; P[k]; k++)
        {
            size_type v = sp[k-1];
            while (v != 0 && P[v] != P[k])
                v = sp[v-1];
            sp[k] = (P[v] == P[k])? v + 1 : 0;
        }
        _pattern_len = k;

        /* Compute and store sp'[] from the sp[]. */
        for (k = 1; P[k]; k++)
        {
            if (P[sp[k]] == P[k+1])
                sp[k] = sp[sp[k]];
        }
    }

    size_type count_matches(const char *T) const
    {
        size_type count = 0, i = 0, j = 0;
        for (;;)
        {
            /* Find first mismatch: P[j] <> T[i]. */
            for (; T[i] && P[j] == T[i]; j++, i++);
            
            /* Increment counter if full match. */
            if (P[j] == 0)
                ++count;

            /* Finish if the text is exhausted. */
            if (T[i] == 0)
                break;

            /* Find the next character in P to match against T[i]. */
            if (j == 0)
                i++;
            else
                j = sp[j-1];
        }
        return count;
    }
};

/*
bm_matcher
ac_set_matcher
*/

#endif /* STRMATCH_HPP */
